1. Technical Field
The present invention relates to techniques for performing fast fourier transforms and more particularly to a multiplexed pipeline fast fourier transform processor.
2. Discussion
The discrete Fourier transform plays an important role in the analysis, the design, and the implementation of digital signal processing algorithms and systems. One difficulty with discrete Fourier transforms is that they are computationally expensive, since the amount of computation, and thus the computation time, is approximately proportional to N.sup.2, where N is the number of terms in the Fourier series. Because of this, a number of techniques have been developed to reduce the time required to compute discrete Fourier transforms. Such techniques generally exploit the special properties of the discrete Fourier transform to group terms and thereby reduce the number of multiplications required.
For example, a group of algorithms known as fast fourier transforms (FFTs) decompose the computation of the discrete fourier transform of a sequence of length N into successively smaller discrete fourier transforms. As a result, the computational time is reduced from N.sup.2 to approximately N log.sub.2 N. The two primary ways the fast fourier transform does this is by decimation in time (DIT) and decimation in frequency (DIF). Early FFTs utilized a processing element and a memory where the processing element would first perform the first pass of an N point FFT, and put that in memory. Then the FFT would switch modes and do the second pass on the FFT results which were stored in memory, and so on.
To improve throughput, fast fourier transform pipelines with multiple processing elements were developed. These pipelines utilize a series of processing elements, each performing a single pass of the FFT. The processing elements are cascaded so that they may process multiple passes of an FFT simultaneously and begin processing a subsequent FFT of the same size before completion of the preceding FFT. In a number of applications, the use of multiple size FFTs is required. These applications include MFSK demodulation, spectrum analysis, FIR filtering, and channelizers. Unfortunately, conventional FFT pipelines are generally not useful for different size FFTs since they are configured to perform only an FFT of a particular size. Further, in many applications where small FFTs are required, the large size of such FFT pipelines makes them unattractive. Providing separate processors for each FFT size results in unnecessary duplication of hardware. Further, reconfiguring processors for different size FFTs reduces efficiency by increasing overhead. For example, such overhead includes processors for performing operations such as data routing and processor control. These overhead operations may become a significant portion of the total processing if the data must be flushed from the processor prior to reconfiguration.
An additional problem with FFT pipelines is that there may be a significant amount of idle time while some processing elements are operating and others are not. For example in systems which cannot provide a continuous stream of data to the FFT processor, when beginning a new FFT after waiting for data, some processing elements sit idle while preceding processing elements are performing their FFTs. Likewise, when finishing an FFT prior to new data becoming available, some processing elements sit idle while subsequent processing elements perform their FFTs.
Thus, it would be desirable to provide an FFT pipeline which makes more efficient utilization of its processing elements to reduce the idle time of individual processing elements. Further, it would be desirable to provide a way to permit an FFT pipeline processor of a given size to be utilized for different size FFT computations without requiring reconfiguration or duplication of processing elements. Further, it would be desirable to reduce the overall hardware requirements for FFT pipelines.